/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package co.edu.unal.bioingenium.kbmed.util.data;

/**
 *
 * @author Alejandro Riveros Cruz
 */
public class QuickSort {

    /**
     * @param:
     * @return:
     */
    public static void sort(int[] data) {
        quicksort(data, 0, data.length - 1);
    }

    /**
     * @param:
     * @return:
     */
    private static void quicksort(int[] data, int left, int right) {
        if (right <= left) {
            return;
        }
        int i = partition(data, left, right);
        quicksort(data, left, i - 1);
        quicksort(data, i + 1, right);
    }

    /**
     * @param:
     * @return:
     */
    @SuppressWarnings("empty-statement")
    private static int partition(int[] data, int left, int right) {
        int i = left - 1;
        int j = right;
        while (true) {
            while (less(data[++i], data[right]));
            while (less(data[right], data[--j])) {
                if (j == left) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exchange(data, i, j);
        }
        exchange(data, i, right);
        return i;
    }

    /**
     * @param:
     * @return:
     */
    private static boolean less(int x, int y) {
        return (x > y);
    }

    /**
     * @param:
     * @return:
     */
    private static void exchange(int[] data, int i, int j) {
        int swap = data[i];
        data[i] = data[j];
        data[j] = swap;
    }

    /**
     * @param:
     * @return:
     */
    public static void sort(int[] data, Object[] relatedData) {
        quicksort(data, relatedData, 0, data.length - 1);
    }

    /**
     * @param:
     * @return:
     */
    private static void quicksort(int[] sortBy, Object[] relatedData, int left, int right) {
        if (right <= left) {
            return;
        }
        int i = partition(sortBy, relatedData, left, right);
        quicksort(sortBy, relatedData, left, i - 1);
        quicksort(sortBy, relatedData, i + 1, right);
    }

    /**
     * @param:
     * @return:
     */
    @SuppressWarnings("empty-statement")
    private static int partition(int[] sortBy, Object[] relatedData, int left, int right) {
        int i = left - 1;
        int j = right;
        while (true) {
            while (less(sortBy[++i], sortBy[right]));
            while (less(sortBy[right], sortBy[--j])) {
                if (j == left) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exchange(sortBy, relatedData, i, j);
        }
        exchange(sortBy, relatedData, i, right);
        return i;
    }

    /**
     * @param:
     * @return:
     */
    private static void exchange(int[] sortBy, Object[] relatedData, int i, int j) {
        int swap = sortBy[i];
        sortBy[i] = sortBy[j];
        sortBy[j] = swap;
        Object swapObj = relatedData[i];
        relatedData[i] = relatedData[j];
        relatedData[j] = swapObj;
    }
}
